﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using System.IO;
using GraphModel.Graph;
using System.Collections;
using GraphModel;


namespace Diagrams
{
    public partial class Form1 : Form
    {
        Diagram diagram = new Diagram();

        public Form1()
        {
            InitializeComponent();
            miNewDiagram_Click(null, null);
        }

        private void miExit_Click(object sender, EventArgs e)
        {
            Close();
        }

        private void miNewDiagram_Click(object sender, EventArgs e)
        {
            diagram = new Diagram();
            dbDiagram.Diagram = diagram;
        }

        private void miSave_Click(object sender, EventArgs e)
        {
            if (sfdDiagram.ShowDialog() == DialogResult.OK)
                diagram.Save(sfdDiagram.FileName);
        }

        private void miLoad_Click(object sender, EventArgs e)
        {
            if (ofdDiagram.ShowDialog() == DialogResult.OK)
            {
                diagram = Diagram.Load(ofdDiagram.FileName);
                dbDiagram.Diagram = diagram;
            }
        }

        private void miExport_Click(object sender, EventArgs e)
        {
            if (sfdImage.ShowDialog() == DialogResult.OK)
            {
                if(sfdImage.FilterIndex == 1)
                    dbDiagram.GetImage().Save(sfdImage.FileName);
                if (sfdImage.FilterIndex == 2)
                    dbDiagram.SaveAsMetafile(sfdImage.FileName);
            }
        }

        // create a Graph object
        private Graph<string> SoCalMap = new Graph<string>();

        // create a Hashtable for the shortest distance and paths
        private Hashtable dist = new Hashtable();
        private Hashtable route = new Hashtable();

        private void ReloadGraphData()
        {
            SoCalMap.Clear();
            dist.Clear();
            route.Clear();

            try
            {
                foreach (Figure figure in diagram.figures)
                {
                    if (figure is LineFigure)
                    {
                        LineFigure line = figure as LineFigure;
                        if (line != null && line.From != null && line.To != null)
                        {
                            string city1 = line.From.text;
                            string city2 = line.To.text;
                            int distance = Convert.ToInt32(line.text);

                            // add the nodes to the graph, if needed
                            if (!SoCalMap.Contains(city1))
                                SoCalMap.AddNode(city1);

                            if (!SoCalMap.Contains(city2))
                                SoCalMap.AddNode(city2);

                            SoCalMap.AddUndirectedEdge(city1, city2, distance);
                        }
                    }
                }
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }
        }

        private void OnRunDijkstra(object sender, EventArgs e)
        {
            ReloadGraphData();

            string start = diagram.FirstFigureName;
            string end = diagram.LastFigureName;

            if (String.IsNullOrEmpty(start) || String.IsNullOrEmpty(end) || !SoCalMap.Contains(start) || !SoCalMap.Contains(end))
            {
                MessageBox.Show("First and Last nodes are not setup corectly.");
                return;
            }

            InitDistRouteTables(start);		// initialize the route & distance tables

            //CheckForm checkForm = new CheckForm(checkEntities);
            //checkForm.ShowDialog();

            NodeList<string> nodes = SoCalMap.Nodes;	// nodes == Q

            /**** START DIJKSTRA ****/
            while (nodes.Count > 0)
            {
                GraphNode<string> u = GetMin(nodes);		// get the minimum node
                nodes.Remove(u);			// remove it from the set Q

                // iterate through all of u's neighbors
                if (u.Neighbors != null)
                    for (int i = 0; i < u.Neighbors.Count; i++)
                        Relax(u.Value, u.Neighbors[i].Value, u.Costs[i]);		// relax each edge
            }	// repeat until Q is empty
            /**** END DIJKSTRA ****/

            // Display results
            StringBuilder sb = new StringBuilder();
            sb.AppendFormat("The shortest path from {0} to {1} is {2} miles and goes as follows: ", start, end, dist[end]);
            sb.Append(Environment.NewLine);
            sb.Append(Environment.NewLine);
            //string results = "The shortest path from " + start + " to " + end + " is " + dist[end].ToString() + " miles and goes as follows: ";

            Stack traceBackSteps = new Stack();

            string current = end, prev = null;
            do
            {
                prev = current;
                current = (string)route[current];

                string temp = current + " to " + prev + Environment.NewLine;
                traceBackSteps.Push(temp);
            } while (current != start);

            //StringBuilder sb = new StringBuilder(30 * traceBackSteps.Count);
            while (traceBackSteps.Count > 0)
                sb.Append((string)traceBackSteps.Pop());

            MessageBox.Show(sb.ToString());

            //Запись в файл
            SaveFileDialog saveFileDialog = new SaveFileDialog();
            saveFileDialog.Filter = "txt files (*.txt)|*.txt|All files (*.*)|*.*";
            saveFileDialog.FilterIndex = 1;
            saveFileDialog.RestoreDirectory = true;
            Stream stream;

            if (saveFileDialog.ShowDialog() == DialogResult.OK)
            {
                if ((stream = saveFileDialog.OpenFile()) != null)
                {
                    using (StreamWriter streamWriter = new StreamWriter(stream))
                    {
                        streamWriter.Write(sb.ToString());
                    }
                    stream.Close();
                }
            }
        }

        /// <summary>
        /// Initializes the distance and route tables used for Dijkstra's Algorithm.
        /// </summary>
        /// <param name="start">The <b>Key</b> to the source Node.</param>
        private void InitDistRouteTables(string start)
        {
            // set the initial distance and route for each city in the graph
            foreach (string cname in SoCalMap)
            {
                dist.Add(cname, Int32.MaxValue);
                route.Add(cname, null);
            }

            // set the initial distance of start to 0
            dist[start] = 0;
        }

        /// <summary>
        /// Relaxes the edge from the Node uCity to vCity.
        /// </summary>
        /// <param name="cost">The distance between uCity and vCity.</param>
        private void Relax(string uCity, string vCity, int cost)
        {
            int distTouCity = (int)dist[uCity];
            int distTovCity = (int)dist[vCity];

            if (distTovCity > distTouCity + cost)
            {
                // update distance and route
                dist[vCity] = distTouCity + cost;
                route[vCity] = uCity;
            }
        }

        /// <summary>
        /// Retrieves the Node from the passed-in NodeList that has the <i>smallest</i> value in the distance table.
        /// </summary>
        /// <remarks>This method of grabbing the smallest Node gives Dijkstra's Algorithm a running time of
        /// O(<i>n</i><sup>2</sup>), where <i>n</i> is the number of nodes in the graph.  A better approach is to
        /// use a <i>priority queue</i> data structure to store the nodes, rather than an array.  Using a priority queue
        /// will improve Dijkstra's running time to O(E lg <i>n</i>), where E is the number of edges.  This approach is
        /// preferred for sparse graphs.  For more information on this, consult the README included in the download.</remarks>
        private GraphNode<string> GetMin(NodeList<string> nodes)
        {
            // find the node in nodes with the smallest distance value
            int minDist = Int32.MaxValue;
            GraphNode<string> minNode = null;
            foreach (GraphNode<string> n in nodes)
            {
                if (((int)dist[n.Value]) <= minDist)
                {
                    minDist = (int)dist[n.Value];
                    minNode = n;
                }
            }

            return minNode;
        }
    }
}
